package cn.pugle.oj.leetcode;

import cn.pugle.oj.catalog.HeapProblem;

import java.util.Arrays;
import java.util.Objects;

/**
 * 多路归并, 堆
 *
 * @author tzp
 * @since 2020/10/15
 */
public class LC23 implements HeapProblem {

    int heapSize;

    public ListNode mergeKLists(ListNode[] arr) {
        if (arr == null || arr.length == 0) return null;
        arr = Arrays.stream(arr).filter(Objects::nonNull).toArray(ListNode[]::new);

        this.heapSize = arr.length;
        heapify(arr);
        ListNode dummyRoot = new ListNode(-1), preNode = dummyRoot;
        while (heapSize > 0) {
            ListNode node = strangePop(arr);
            preNode.next = node;
            preNode = node;
        }
        return dummyRoot.next;
    }

    //--- 堆相关方法, 小顶堆

    public ListNode strangePop(ListNode[] heap) {
        ListNode result = heap[0];
        if (heap[0].next != null) {
            heap[0] = heap[0].next;
            siftDown(heap, 0);
        } else {
            heap[0] = heap[heapSize - 1];
            heap[heapSize - 1] = null;
            heapSize--;
            siftDown(heap, 0);
        }
        return result;
    }

    public void heapify(ListNode[] lists) {
        for (int i = lists.length / 2 - 1; i >= 0; i--) {
            siftDown(lists, i);
        }
    }

    public void siftUp(ListNode[] heap, int index) {
    }

    public void siftDown(ListNode[] heap, int index) {
        int leftC = leftChild(index);
        int rightC = rightChild(index);
        if (leftC < heapSize) {//有孩子
            int smallChild = rightC >= heapSize ? leftC :
                    heap[leftC].val > heap[rightC].val ? rightC : leftC;
            if (heap[index].val > heap[smallChild].val) {
                swap(heap, index, smallChild);
                siftDown(heap, smallChild);
            }
        }
    }

    public int leftChild(int index) {
        return 2 * index + 1;
    }

    public int rightChild(int index) {
        return 2 * index + 2;
    }

    public int parent(int index) {
        return (index - 1) / 2;
    }

    public void swap(ListNode[] heap, int i, int j) {
        ListNode tmp = heap[i];
        heap[i] = heap[j];
        heap[j] = tmp;
    }

    public static void main(String[] args) {
        ListNode a = ListNode.arrayToListNode(new int[]{1, 4, 5});
        ListNode b = ListNode.arrayToListNode(new int[]{3, 3, 4});
        ListNode c = ListNode.arrayToListNode(new int[]{2, 6});
        System.out.println(new LC23().mergeKLists(new ListNode[]{}));
        System.out.println(new LC23().mergeKLists(new ListNode[]{null}));
        System.out.println(new LC23().mergeKLists(new ListNode[]{null, a}));
        System.out.println(new LC23().mergeKLists(new ListNode[]{a, b, c}));
    }
}
